package org.example.leetCode;

/**
 * 64. 最小路径和
 * 给定一个包含非负整数的 m x n 网格 grid ，
 * 请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 */
public class Code64 {
    public static int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for(int row=0;row<m;row++){
            for(int col=0;col<n;col++){
                if(row==0&&col==0){
                    continue;
                }else if(row==0){
                    grid[row][col]=grid[row][col]+grid[row][col-1];
                }else if(col==0){
                    grid[row][col]=grid[row][col]+grid[row-1][col];
                }else{
                    grid[row][col]=grid[row][col]+Math.min(grid[row-1][col],grid[row][col-1]);
                }
            }
        }
        return grid[m-1][n-1];
    }

    public static void main(String[] args) {

        // 示例网格
        int[][] grid = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };

        // 调用方法并输出结果
        int result = minPathSum(grid);
        System.out.println("最小路径和为: " + result); // 预期输出：7（路径 1→3→1→1）
    }
}
